package day_2022_4_to_7.nowcoder;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author haomin
 * @date 2022/05/08 14:21
 **/
public class TreeDepth_29f {
    // 方法一 递归
    public int TreeDepth(TreeNode root) {
        // 递到叶子节点时归，
        if(root == null){
            return 0;
        }
        // 当每次递时 + 1，取左右孩子归的最大值
        return 1 + Math.max(TreeDepth(root.left),TreeDepth(root.right));
    }

    // 方法二 迭代
    public int TreeDepth2(TreeNode root) {
        if (root == null) {
            return 0;
        }
        // 1.设置一个队列，并将根节点入队
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int depth = 0;
        // 2. 如果队列不为空,当前队列中所有节点出队
        while (!queue.isEmpty()) {
            // （将一层节点出队depth+= 1）
            depth++;
            int size = queue.size();
            // 就将当前队列中所有节点出队
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();

                // 3. 出队时将该节点的左右孩子入队
                if(node.left != null) queue.offer(node.left);
                if(node.right != null) queue.offer(node.right);
            }
        }
        // 4. 走到这，说明当队列为空，每层节点都进行了入队出队操作，depth 值就是树的深度
        return depth;
    }
}